import java.util.*;
public class chap02 {
    public static void main(String[] args) {
        System.out.println("请输入你要进行排序的数字个数：");
        Scanner input1 = new Scanner(System.in);
        // 输入进行排序的数字个数，控制在100以内
        int num = input1.nextInt();
        int[] a = new int[num];
        int k = 0;
        while (k <= num - 1) {

            int t = (int) (Math.random() * 1000);
            // 随机产生0-1000范围内的数字，并确保不重复

            boolean b = false;

            for (int i = 0; i < a.length; i++) {

                if (t == a[i]) {

                    b = true;

                }

            }

            if (b != true) {

                a[k] = t;

                k++;

            }

        }

        input1.close();

        int[] templist = new int[a.length];
        System.arraycopy(a, 0, templist, 0, a.length);

        System.out.println("初始状态： " + Arrays.toString(a) + " 下面进行直接插入排序"); // 输入序列的最初状态

        int[] b = InserSort(a);

        System.out.println("经过直接插入排序后最终状态： " + Arrays.toString(b)); // 输入排序后序列的最终状态

        System.arraycopy(templist, 0, a, 0, templist.length);

        System.out.println("\n\n初始状态： " + Arrays.toString(a) + " 下面进行冒泡排序"); // 输入序列的最初状态

        int[] c = BubbleSort(a);

        System.out.println("经过冒泡排序后最终状态： " + Arrays.toString(c)); // 输入排序后序列的最终状态

        System.arraycopy(templist, 0, a, 0, templist.length);

        System.out.println("\n\n初始状态： " + Arrays.toString(a) + " 下面进行希尔排序"); // 输入序列的最初状态

        int[] d = ShellSort(a);

        System.out.println("经过希尔排序后最终状态： " + Arrays.toString(d)); // 输入排序后序列的最终状态

    }

    public static int[] InserSort(int[] a) { // 直接插入算法 insertion sort

        int i, j, num = 0;

        // 角标从第二个值开始，遍历所有值

        for (i = 1; i < a.length; i++) {

            // 每次排序a[i]与前面的所有值比较

            for (j = 0; j <= i; j++) {

                // 如果大，则前面的数据不动

                if (a[i] < a[j]) {

                    // 如果小，则插入到数列中，所有数据往后移动

                    int temp = a[i];

                    for (int k = i; k > j; k--) {

                        a[k] = a[k - 1];

                    }

                    a[j] = temp;

                }

            }

            System.out.println("第 " + (++num) + " 趟排序： " + Arrays.toString(a));

        }

        return a;

    }

    public static int[] BubbleSort(int[] a) { // 冒泡算法 bubble sort

        int n = a.length;

        for (int i = 0; i < n - 1; i++) {

            for (int j = 0; j < n - i - 1; j++) {

                if (a[j] > a[j + 1]) {

                    // 交换 a[j] 和 a[j+1]

                    int temp = a[j];

                    a[j] = a[j + 1];

                    a[j + 1] = temp;

                }

            }

            System.out.println("第 " + (i + 1) + " 趟排序： " + Arrays.toString(a));

        }

        return a;

    }

    public static int[] ShellSort(int[] a) { // 希尔排序算法 Shell Sort
        int n = a.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = a[i];
                int j;
                for (j = i; j >= gap && a[j - gap] > temp; j -= gap) {
                    a[j] = a[j - gap];
                }
                a[j] = temp;
            }
            System.out.println("间隔为 " + gap + " 的排序： " + Arrays.toString(a));
        }
        return a;
    }

}